Search for: All records

Man-made and natural disruptions such as planned constructions on roads, suspensions of bridges, and blocked roads by trees/mudslides/floods can often create obstacles that separate two connected regions. As a result, the traveling and reachability of agents from their respective regions to other regions can be affected. To minimize the impact of the obstacles and maintain agent accessibility, we initiate the problem of constructing a new pathway (e.g., a detour or new bridge) connecting the regions disconnected by obstacles from the mechanism design perspective. In the problem, each agent in their region has a private location and is required to access the other region. The cost of an agent is the distance from their location to the other region via the pathway. Our goal is to design strategyproof mechanisms that elicit truthful locations from the agents and approximately optimize the social or maximum cost of agents by determining locations in the regions for building a pathway. We provide a characterization of all strategyproof and anonymous mechanisms. For the social and maximum costs, we provide upper and lower bounds on the approximation ratios of strategyproof mechanisms. 

We study a variation of facility location problems (FLPs) that aims to improve the accessibility of agents to the facility within the context of mechanism design without money. In such a variation, agents have preferences on the ideal locations of the facility on a real line, and the facility’s location is fixed in advance where (re)locating the facility is not possible due to various constraints (e.g., limited space and construction costs). To improve the accessibility of agents to facilities, existing mechanism design literature in FLPs has proposed to structurally modify the real line (e.g., by adding a new interval) or provide shuttle services between two points when structural modifications are not possible. In this paper, we focus on the latter approach and propose to construct an accessibility range to extend the accessibility of the facility. In the range, agents can receive accommodations (e.g., school buses, campus shuttles, or pickup services) to help reach the facility. Therefore, the cost of each agent is the distance from their ideal location to the facility (possibility) through the range. We focus on designing strategyproof mechanisms that elicit true ideal locations from the agents and construct accessibility ranges (intervals) to approximately minimize the social cost or the maximum cost of agents. For both social and maximum costs, we design group strategyproof mechanisms and strong group strategyproof mechanisms with (asymptotically) tight bounds on the approximation ratios. 

Abstract Colonoscopy is accurate but inefficient for colorectal cancer (CRC) prevention due to the low (~ 7 to 8%) prevalence of target lesions, advanced adenomas. We leveraged rectal mucosa to identify patients who harbor CRC field carcinogenesis by evaluating chromatin 3D architecture. Supranucleosomal disordered chromatin chains (~ 5 to 20 nm, ~1 kbp) fold into chromatin packing domains (~ 100 to 200 nm, ~ 100 to 1000 kbp). In turn, the fractal-like conformation of DNA within chromatin domains and the folding of the genome into packing domains has been shown to influence multiple facets of gene transcription, including the transcriptional plasticity of cancer cells. We deployed an optical spectroscopic nanosensing technique, chromatin-sensitive partial wave spectroscopic microscopy (csPWS), to evaluate the packing density scaling D of the chromatin chain conformation within packing domains from rectal mucosa in 256 patients with varying degrees of progression to colorectal cancer. We found average packing scaling D of chromatin domains was elevated in tumor cells, histologically normal-appearing cells 4 cm proximal to the tumor, and histologically normal-appearing rectal mucosa compared to cells from control patients (p < 0.001). Nuclear D had a robust correlation with the model of 5-year risk of CRC with r² = 0.94. Furthermore, rectal D was evaluated as a screening biomarker for patients with advanced adenomas presenting an AUC of 0.85 and 85% sensitivity and specificity. artificial intelligence-enhanced csPWS improved diagnostic performance with AUC = 0.90. Considering the low sensitivity of existing CRC tests, including liquid biopsies, to early-stage cancers our work highlights the potential of chromatin biomarkers of field carcinogenesis in detecting early, significant precancerous colon lesions. 

Abstract Supranucleosomal chromatin structure, including chromatin domain conformation, is involved in the regulation of gene expression and its dysregulation has been associated with carcinogenesis. Prior studies have shown that cells in the buccal mucosa carry a molecular signature of lung cancer among the cigarette-smoking population, the phenomenon known as field carcinogenesis or field of injury. Thus, we hypothesized that chromatin structural changes in buccal mucosa can be predictive of lung cancer. However, the small size of the chromatin chain (approximately 20 nm) folded into chromatin packing domains, themselves typically below 300 nm in diameter, preclude the detection of alterations in intradomain chromatin conformation using diffraction-limited optical microscopy. In this study, we developed an optical spectroscopic statistical nanosensing technique to detect chromatin packing domain changes in buccal mucosa as a lung cancer biomarker: chromatin-sensitive partial wave spectroscopic microscopy (csPWS). Artificial intelligence (AI) was applied to csPWS measurements of chromatin alterations to enhance diagnostic performance. Our AI-enhanced buccal csPWS nanocytology of 179 patients at two clinical sites distinguished Stage-I lung cancer versus cancer-free controls with an area under the ROC curve (AUC) of 0.92 ± 0.06 for Site 1 (in-state location) and 0.82 ± 0.11 for Site 2 (out-of-state location).